package leetcode_900;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *MinimumCostToHireKWorkers_857_ 给定N个工人的 quality和wage数值  要求从中选K个工人 其分配工资比例相同 且都满足最低工资期望
 *describe:用贪心算法+堆实现 若选定了K个工人 那么分配工资的最优方案是选择W/Q最高的那个 做比例  不然其他人工资要调高 整体代价要升高
 *那么给Worker按照ratio排序 最优解从ratio第k个到第n个中选出 其中最优方案是Q最高 则最后付出最低  AC 65%
 *2018年11月5日 上午10:08:50
 */
public class MinimumCostToHireKWorkers_857_ {
	class Worker{
		int quality;
		double ratio;
		public Worker(int quality,int wage) {
			this.quality=quality;
			this.ratio=(double)wage/quality;
		}	
	}
	
	public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        PriorityQueue<Integer> queue=new PriorityQueue<Integer>();//优先队列保证q的总和 因此要保存最小到大的值 取负数-Q
        Worker []workers=new Worker[quality.length];
        for(int i=0;i<quality.length;++i)
        	workers[i]=new Worker(quality[i], wage[i]);
        Arrays.sort(workers,(o1,o2)->Double.compare(o1.ratio, o2.ratio));//按照ratio排序  此处时间复杂度O(nlogn)
        double res=Double.MAX_VALUE;
        int sum=0;
        for(Worker worker:workers) {//前面都是w/q 较低的
        	queue.offer(-worker.quality);//因为要保留n个quality最大的 所以堆里放负数
        	sum+=worker.quality;
        	if(queue.size()>K) {
        		sum+=queue.poll();//相当于把最小的减去
        	}
        	if(queue.size()==K) {
        		res=Math.min(res, worker.ratio*sum);
        	}
        }
        return res;
    }
}
